﻿#light

//Tsts frrom the papper

//flip flip

type Elem = int

type Tree = Empty | Branch of Elem*Tree*Tree

let testTree = Branch(1, Branch(2,Empty,Empty), Branch(3,Empty,Empty))

let rec flip (t:Tree) = 
    match t with
    | Empty -> Empty
    | Branch(l, a, b) -> Branch(l, flip(b), flip(a))
    
let rec insert (x:int) (t:Tree) :Tree = 
    match t with
        | Empty -> Branch(x, Empty, Empty)
        | Branch(y, a, b) when x < y -> Branch(y, (insert x a), b)
        | Branch(y, a, b) when y < x -> Branch(y, a, (insert x b))
        
let rec insertList (xs:int list) (t:Tree) :Tree= 
    match xs with
        | [] -> t
        | x::xs -> insertList xs (insert x t)

let genTree n = insertList [(-n/2)..0] (insertList [1..(n/2)] Empty)

let rec printTree (t:Tree) = 
    match t with
        | Empty -> printf "Empty"
        | Branch(x, a, b) -> printf "%d" x
                             printTree a
                             printf "\n"
                             printTree b

let rec h3 zt = 
    match zt with
    | Empty -> Empty
    | Branch(l, a, b) -> Branch(l, h3(a), h3(b))
        

let paperTest3 t = flip (flip t)
let DpaperTest3 t = h3 t
        
//sum (map spuare (upto 1 n))
let square x = x*x

//n<1861
let paperTest (n:int) :int = List.sum (List.map square [1..n])

let rec h a m n = 
    match m > n with
        | true -> a
        | _ -> h (a+square m) (m+1) n

let DpaperTest n = h 0 1 n


//append append

let rec myAppend xs ys = 
    match xs with
        | [] -> ys
        | (head::tail) -> head::(myAppend tail ys)

let paperTest2 xs ys zs = List.append (List.append xs ys) zs


//Fulhax
let paperTest2int (n : int) = paperTest2 [1..n] [1..n] [1..n]

let rec h1 ys zs = 
    match ys with
        | [] -> []
        | (y::ys) -> y :: (h1 ys zs)

let rec h0 xs ys zs = 
    match xs with
        | [] -> h1 ys zs
        | (x::xs) -> x :: (h0 xs ys zs)

let DpaperTest2 xs ys zs = h0 xs ys zs

let DpaperTest2int n = DpaperTest2 [1..n] [1..n] [1..n]


//Preformanstests on the tests
let rec TestInt2 (timesTestedCounter:int) (timesTested:int) (input:int) (avg:int) testFunction deforestedTestFunction = 
    match timesTestedCounter with
        | 0 -> printf "%d.%d" (avg/timesTested) (avg%timesTested)
        | _ -> printfn "%d" (timesTested-timesTestedCounter+1)
               let s1 = System.DateTime.UtcNow
               let f = (testFunction input)
               let ft = (System.DateTime.UtcNow - s1).Milliseconds
               printfn "function Execution time: %d" ft
    
               let s2 = System.DateTime.UtcNow
               let d = (deforestedTestFunction input)
               let dt = (System.DateTime.UtcNow - s2).Milliseconds
               printfn "Deforested Execution time: %d" dt
               
               printfn "%b\n\n" (f.Equals d)
               
               let avg2 = avg + ft-dt
               
               TestInt2 (timesTestedCounter-1) timesTested input avg2 testFunction deforestedTestFunction
               
let TestInt (timesTested:int) (input:int) testFunction deforestedTestFunction = TestInt2 timesTested timesTested input 0 testFunction deforestedTestFunction

let rec TestTree2 (timesTestedCounter:int) (timesTested:int) (input:Tree) (avg:int) testFunction deforestedTestFunction = 
    match timesTestedCounter with
        | 0 -> printf "%d.%d" (avg/timesTested) (avg%timesTested)
        | _ -> printfn "%d" (timesTested-timesTestedCounter+1)
               let s1 = System.DateTime.UtcNow
               let f = (testFunction input)
               let ft = (System.DateTime.UtcNow - s1).Milliseconds
               printfn "function Execution time: %d" ft
    
               let s2 = System.DateTime.UtcNow
               let d = (deforestedTestFunction input)
               let dt = (System.DateTime.UtcNow - s2).Milliseconds
               printfn "Deforested Execution time: %d" dt
               
               printfn "%b\n\n" (f.Equals d)
               
               let avg2 = avg + ft-dt
               
               TestTree2 (timesTestedCounter-1) timesTested input avg2 testFunction deforestedTestFunction
               
let TestTree (timesTested:int) (input:Tree) testFunction deforestedTestFunction = TestTree2 timesTested timesTested input 0 testFunction deforestedTestFunction
               

               

let rec intMemTest (f:int->int) (input:int) (inc:int) :int = 
    match input with
        | -1 -> -1
        | _ -> printfn "input: %d" input
               f input
               intMemTest f (input+inc) inc

let rec intMemTestList (f:int->int list) (input:int) (inc:int) :int = 
    match input with
        | -1 -> -1
        | _ -> printfn "input: %d" input
               f input
               intMemTestList f (input+inc) inc

let rec intMemTestTree (f:Tree->Tree) (input:int) (inc:int) :int = 
    match input with
        | -1 -> -1
        | _ -> printfn "input: %d" input
               f (genTree input)
               intMemTestTree f (input+inc) inc

//Tets the memory of sum (map square [1..n])
let memTest1 = intMemTest paperTest 1500 50

//Tsets the memory of append (append xs ys) zs
let memTest2 = intMemTestList DpaperTest2int 3260 1

//Tsets the memory of flip (flip t)
let memTest3 = intMemTestTree paperTest3 6905 1

[<EntryPoint>]
let Main args = 
    //let r = TestInt 20 1860 paperTest DpaperTest
    let i1 = 1860
    let i2 = 3262
    let i3 = 6909
    let i4 = 10000000
    
    //Memory tests
//    paperTest i1
//    DpaperTest i4
//    paperTest2int i4
//    DpaperTest2int i2
//    paperTest3 i3
//    DpaperTest3 i3
    
    //Execution tests
    //Compares te average times faster teh deforestatded version is in ms
    let times = 9000
//    TestInt times i1 paperTest DpaperTest
//    TestInt 2 i2 paperTest2int DpaperTest2int
//    TestTree times (genTree i3) paperTest3 DpaperTest3
    
    0